A19 - Knapsack 1 - 競プロ

A19 - Knapsack 1

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_s

提出

code: python

n, w = map(int, input().split())

wv = list(map(int, input().split())) for _ in range(n)

# print(wv)

# 3, 13], 3, 17, 5, 29, [1, 10

# dpij := i 個目までで重さ j の時の価値の最大値

dp = [0 * (w+1) for _ in range(n+1)]

for i in range(1, n+1):

for j in range()

解答

code: python

n, w = map(int, input().split())

wv = list(map(int, input().split())) for _ in range(n)

# print(wv)

# 3, 13], 3, 17, 5, 29, [1, 10

# dpij := i 個目までで重さ j の時の価値の最大値

dp = [0 * (w+1) for _ in range(n+1)]

dp00 = 0

for i in range(1, n+1):

for j in range(0, w+1):

weight, value = wvi-1

if j < weight:

dpij = dpi-1j

if j >= weight:

# i-1 の時点で: 合計が j であり、i を選ばない vs 合計が j-weight であり、i を選ぶ

dpij = max(dpi-1j, dpi-1j-weight+value)

# 合計がちょうど w のとき価値が最大になるとは限らない

print(max(dpn))